from typing import List

"""
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
"""


class Solution:

    def jump(self, nums: List[int]) ->int:
        n=len(nums)
        if(n==0):
            return 0
        dp=[9999]*n
        dp[0]=0
        for i in range(n):
            for j in range(1,nums[i]+1):
                if(i+j<n):
                    dp[i+j]=min(dp[i]+1,dp[i+j])
        return dp[-1]




    def jump2(self, nums: List[int]) -> int:
        memo = {}

        def dfs(start):
            if start >= len(nums) - 1:
                return 0
            if start in memo:
                return memo[start]

            min_jumps = float('inf')
            for i in range(1, nums[start] + 1):
                jumps = dfs(start + i)
                if jumps != float('inf'):
                    min_jumps = min(min_jumps, jumps + 1)

            memo[start] = min_jumps
            return min_jumps

        return dfs(0)


lll = Solution()
print(lll.jump([2, 3, 1, 1, 4,3]))

